本次实验是在DEV C++软件上进行实现的。语言采用的是c++语言,但在整体上与c语言大致相似(不管用什么语言实现,思想是不变的)。
此次实现的整体思路:首先定义图书这个抽象数据类型,并且定义节点抽象数据类型(根据这些抽象数据类型对下面的数据进行定义)。然后进行单链表的初始化、单链表的取值、单链表的查找、单链表的插入、单链表的删除、尾插法建立单链表。在尾插法建立单链表时使用了文件流读取txt文件,并将其存储到链表中。最后建立主函数,使用主函数调用上述的算法。
具体程序代码如下:
#include
#include
#include
typedef int Status;
using namespace std;
struct Book {
string id;//ISBN
string name;//书名
double price;//价格
};
typedef struct LNode {
Book data;//节点数据
struct LNode *next;//节点指针域
} LNode, *LinkList;//都是LNode的别名,其中LinkList 为指向结构体LNode的指针类型
//单链表的初始化
Status InitList (LinkList &L) {
//构建一个空链表
L = new LNode;//生成新节点作为头节点,头指针L指向头结点
L->next = NULL;//头指针指针域置空。
return 1; //初始化成功返回1.
}
// 单链表的取值
Status GetElem (LinkList L, int i, Book &e) {
//在带头节点的单链表L中查找第i个元素,并赋值给e
LNode *p;
int j;
p = L->next;//初始化,p指向首元节点,计数器初值赋值为1.
j = 1;
while (p && j < i) {//顺着链表往下找,直到p为空或者p指向第i个元素。
p = p->next;
++j;
}
if(!p || j > i) {
cout data;//将*P节点的数据赋值给e。
return 1;//取值成功返回1.
}
//单链表的查找
Status LocateElem (LinkList L,double e) {
//在带头结点的单链表L中查找值为e的元素。
LNode *p;
int j = 1;
p = L->next;//初始化,指针p指向首元节点
while (p && p->data.price != e) {//顺着链表向下查找,直到p为空,或者p所指的数据域等于e。
p = p->next;
++j;
}
return j;//查找成功返回e的节点地址p,失败则返回NULL。
}
//单链表的插入
Status ListInsert (LinkList &L,int i, Book &e) {
LNode * p, * s;
int j = 0;
p = L;
while (p && j < i -1) {//查找第i-1个元素节点,p指向该节点。
p = p->next;
++j;
}
if(!p || j > i - 1) {
cout data = e;//将新节点的数据域置为e。
s->next = p->next;//将节点*s的指针域指向第i个元素。
p->next = s;//将节点*p的指针域指向*s的指针域。
return 1;//插入成功返回1.
}
//单链表的删除
Status ListDelete (LinkList &L, int i) {
LNode *p, *q;
p = L;
int j = 0;
while (p->next && j < i - 1) {//查找第i-1个节点,p指向第i-1个位置。
p = p->next;
++j;
}
if(!(p->next) || j > i - 1) {
cout next;//临时保存被删除节点的地址以备释放。
p->next = q->next;//改变删除节点前驱结点的指针域。
delete q;
return 1;//删除成功返回1.
}
//使用尾插法创建单链表
void CreateList (LinkList &L, int n) {
LinkList p,r;
string head_1,head_2,head_3;
L = new LNode;
L->next = NULL;//先建立一个带头结点的空链表。
r = L;//尾指针r指向头结点
int length = 0;
fstream file;
file.open("book.txt");
if(!file) {
cout > head_2 >> head_3;
while (!file.eof()) {//蒋文件中的信息运用尾插法插入到链表中。
p = new LNode;//生成新节点。
file >> p->data.id >> p->data.name >> p->data.price;//输入元素赋值给新节点的数据域。
p->next = NULL;
r->next = p;//新节点*p插入到尾结点*r之后。
r = p;//r指向新的尾结点*p
length++;//同时对链表的长度进行统计
}
file.close();
}
//构建主函数,调用上述算法
int main() {
int i = 0, n = 0, choose,length = 0;
double price;
Book e;
LinkList L,p;
choose = -1;
cout |